The present invention relates to first-in-first-out (FIFO) data pipelines, and more particularly to techniques for monitoring and indicating partial fullness levels of the FIFO pipelines.
FIFOs are widely used in computer and telecommunication fields for buffering data and handling transfer of data items between producers which deliver data items to the FIFO and consumers which remove data items from the FIFO. FIFOs are typically used as buffers for transferring data items between systems which may be clocked or asynchronous. For clocked systems involved in the transfer of the data items, the clocks may be of different frequencies and/or phases. Such buffers are typically used in systems where data items are produced or consumed in bursts.
FIFO implementations are usually either RAM-based or flow-through designs. The present invention relates to flow-through FIFOs. A flow-through FIFO generally comprises a plurality of stages and has an input port and an output port. Data items enter the FIFO at the input port, progress from one stage of the FIFO to the next, and exit the FIFO at the output port after the last stage of the FIFO. Accordingly, as suggested by the name FIFO (first-in-first-out), the order in which data items exit a FIFO is the same as the order in which the data items entered the FIFO.
When using a FIFO, it is often useful to know the fullness level of a FIFO. For example, a producer of data items needs to know if a FIFO is xe2x80x9calmost fullxe2x80x9d in order to stop sending data items to the FIFO before the FIFO overflows. Similarly, a consumer needs to know when the FIFO is xe2x80x9calmost emptyxe2x80x9d so that the consumer can slow down or stop trying to remove data items from the FIFO. Accordingly, a FIFO generally has signals associated with it which monitor and indicate the fullness level of the FIFO. For example, the indicator signals may indicate if the FIFO is xc2xc full, xc2xd full, xc2xe full, or the like. Such fullness indicator signals are called partial fullness indicator signals. These signals are typically important for producer circuits and consumer circuits to facilitate efficient flow of data items through the FIFO while preventing data loss that can occur if data is delivered to a FIFO that is completely full. These signals can be used to also prevent the consumer from reading from an empty FIFO.
The FIFO partial fullness indicator signals may be implemented relatively easily in RAM-based FIFO designs by knowing the total capacity of the FIFO and by monitoring the difference in value between the read and write pointers of the FIFO. Additionally, RAM-based FIFOs generally have multiple full/empty indicator signals which indicate the precise fullness values of the FIFO when only approximate values are needed. However, implementing partial fullness indicator signals in linear flow-through FIFOs is more complex, because monitoring the fullness or emptiness of individual stages of a FIFO does not generally yield steady signals as the fullness of a particular stage can be transitory and changes from empty to full and then back to empty again as a data item passes through the stage.
FIG. 1A depicts a conventional technique for producing partial fullness signals 24 for a linear FIFO 10. Signals di and do represent the data input and data output of FIFO 10 respectively. Control signals request input ri, request output ro, acknowledge input ai, and acknowledge output ao facilitate the transfer of data items to and from FIFO 10. Request input signal ri indicates to FIFO 10 that a data item appearing at input di is valid and available to be stored by the first stage of FIFO 10. Request output signal ro indicates to a consumer that the data items appearing on output do is valid and available to be read from FIFO 10. Acknowledgment input signal ai indicates that the data item appearing on data input di has been stored in FIFO 10. Acknowledgment output signal ao informs FIFO 10 that the data item appearing on data output do has been read.
The embodiment shown in FIG. 1A uses an up-down counter 12 to measure the partial fullness of FIFO 10. Counter 12 generally has a lower bound value of zero, indicating an empty FIFO, and a upper bound value equal to the maximum capacity of FIFO 10, indicating a full FIFO. Counter 12 is incremented as data items are loaded into FIFO 10 via input port 14, and decremented as data items are read from FIFO 10 via output port 16. Although counter 12 is able to produce partial fullness signals, it suffers from several disadvantages. For example, counter 12 has to be carefully designed to accommodate independent count up 18 and count down 20 signals, and requires the use of an arbiter 22 to arbitrate the count up and count down requests as both these signals can be received at about the same time. Another disadvantage of such a counter is that the entry of a second data item into FIFO 10 must wait not just for the first data item to be stored in FIFO 10, but also for the count value to be incremented. This adversely affects the efficiency of FIFO 10. The C-elements and RGD Arbiter 22 are components well known to asynchronous circuit designers.
FIG. 1B depicts another conventional technique for producing a partial fullness indicator signal 40 for a linear FIFO 30. According to this technique, the fullness/emptiness of each individual stage of FIFO 30 is monitored to determine the partial fullness or partial emptiness of FIFO 30. As shown in FIG. 2, a resistor 32 is coupled to each individual FIFO stage and to a common node 34. A capacitor 36 is coupled between common node 34 and ground voltage 38. The voltage across each resistor is at a first voltage level when the stage connected to the resistor is full, and at a different voltage level when the stage is empty. Since the fullness of any stage carries the same weight as the fullness of any other stage, the voltage on capacitor 36 indicates the proportion of full stages in FIFO 30. FIFO partial fullness indicator signals 40 are obtained using voltage comparators 42 to compare the voltage on capacitor 36 with some reference voltages 44. A variant of this scheme uses currents rather than voltages to produce the fullness signals. Although this technique produces partial fullness indicator signals for a linear FIFO, this technique is quite expensive to implement. Since the voltage for each stage has to be measured, this technique requires a significant amount of additional circuitry, for example resistors connected to each stage, capacitor, comparators, etc., to produce the partial fullness signals. For large FIFOs, this technique requires a large number of wires to convey the fullness of each stage, and these wires are generally the expensive item in a chip. Due to the need for increased circuitry, this technique also reduces the amount of real estate available on a chip.
Thus, there is a need for techniques which can efficiently and accurately provide partial fullness indicator signals for a FIFO using minimal circuitry. It is desired that these techniques be able to generate fullness signals without having to monitor the fullness/emptiness of each individual stage of the FIFO.
The present invention relates to techniques for indicating partial fullness levels of a FIFO comprising a plurality of stages. A partial fullness detector is coupled to a subset of the plurality of stages of the FIFO, and is configured to output a signal indicating a partial fullness level of the FIFO.
According to an embodiment of the present invention, a m-out-of-n (where mxe2x89xa6n) detector is used to output signals indicating the partial fullness level of a FIFO. The m-out-of-n detector is coupled to xe2x80x9cnxe2x80x9d stages of the FIFO and configured to output partial fullness indicator signals based on the full/empty states of the stages coupled to the m-out-of-n detector. The fullness levels indicated by embodiments of the present invention may include xc2xd full, xc2xc full, ⅓ full, ⅔ full, or any other fractional fullness measures between 0 and 1, where 0 indicates an empty FIFO and 1 indicates a completely full FIFO.
According to an embodiment of the present invention, the m-out-of-n detector is configured to output the partial fullness indicator signal in a first state when xe2x80x9cmxe2x80x9d stages coupled to the m-out-of-n detector are full, and to output the partial fullness indicator signal in a second state when xe2x80x9cmxe2x80x9d stages coupled to the m-out-of-n detector are empty.
According to another embodiment of the present invention, the number of full stages of the FIFO lies in a first range when the m-out-of-n detector outputs the signal in the first state, and in a second range when the m-out-of-n detector outputs the signal in the second state. The bounds for the ranges may be determined based on the input and output rate characteristics and characteristics of the FIFO. According to an embodiment, the range of the number of full stages may be calculated based upon performance parameters associated with the FIFO and maximum data rates of a producer sending data to the FIFO and a consumer removing data from the FIFO.
According to yet another embodiment of the present invention, a m-out-of-n detector may be used to determine the partial fullness of a serial-concurrent-serial (SCS) FIFO comprising a plurality of branches each comprising a plurality of stages. In this embodiment, the m-out-of-n detector may be coupled to xe2x80x9cnxe2x80x9d stages of the SCS FIFO and configured to output a partial fullness indicator signal indicating a fullness level of the SCS FIFO. The m-out-of-n detector may be configured to output the partial fullness indicator signal in a first state when xe2x80x9cmxe2x80x9d stages coupled to the m-out-of-n detector are full, and to output the signal in a second state when xe2x80x9cmxe2x80x9d stages coupled to the m-out-of-n detector are empty.
According to another embodiment of the present invention, m-out-of-n detectors may be used to determine the partial fullness of a rectangular serial-concurrent-serial (SCS) FIFO comprising a distributor, a collector, and column FIFOs comprising a plurality of stages. In such an embodiment, the distributor is configured to distribute data items to the column FIFOs and the collector is configured to collect the data items from the column FIFOs. A first m-out-of-n detector may be coupled to xe2x80x9cnxe2x80x9d stages of a first column FIFO and may be configured to output a first signal indicating a fullness level of the first column FIFO. A second m-out-of-n detector may be coupled to xe2x80x9cnxe2x80x9d stages of a second column FIFO and configured to output a second signal indicating a fullness level of the second column FIFO. The first signal may be used to indicate to the producer when it should stop producing data items to the SCS FIFO. The second signal may be used to indicate to the consumer when it should stop removing data items from the SCS FIFO.